package week_04;

import java.util.Comparator;
import java.util.Map;
import java.util.PriorityQueue;

public class MaxSlidingWindow_heap_239 {
    public class Item {
        int value;
        int index;

        public Item() {

        }

        public Item(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<Item> queue = new PriorityQueue<>(new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o2.value - o1.value;
            }
        });
        //前k个值入priorityDeque
        for (int i = 0; i < k - 1; i++) {
            queue.add(new Item(nums[i], i));
        }
        int[] ans = new int[n - k + 1];
        // 开始插入每次需要新插入的和求max值的节点
        for (int i = k - 1; i < n; i++) {

            // 如果新插入的节点让顶点过期则出栈，如果是不影响结果的非top过期值，晚一些出堆
            while (!queue.isEmpty()&&queue.peek().index <= i - k) queue.poll();
            queue.add(new Item(nums[i], i));
            ans[i - k + 1] = queue.peek().value;
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
        MaxSlidingWindow_heap_239 test = new MaxSlidingWindow_heap_239();
        test.maxSlidingWindow(arr, 3);
    }


}
